﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using ProceduralGolf.generation;

#region buggy code
/*
namespace ProceduralGolf.terrain
{
    class VarianceTree
    {
        public Heightmap Heightmap { get { return heightmap; } }
        //public float[] Tree { get { return variancetree; } }
        public Triangle[] Triangles { get { return triangles; } }

        Heightmap heightmap;
        GolfCourseLayout.GolfCourseLayer[,] layermap;
        float[] variancetree;
        GolfCourseLayout.GolfCourseLayer?[] layertree;
        Triangle[] triangles;

        int width;
        int height;

        public VarianceTree(Heightmap heightmap, GolfCourseLayout.GolfCourseLayer[,] layermap)
        {
            if (heightmap.Width == heightmap.Height &&
                heightmap.Width == layermap.GetLength(0) + 1 &&
                heightmap.Height == layermap.GetLength(1) + 1)
            {
                this.heightmap = heightmap;
                this.layermap = layermap;
                this.width = heightmap.Width - 1;
                this.height = heightmap.Height - 1;
                //int arraySize = 4 * width * height - 1;
                int arraySize = 2 * width * height - 1;
                variancetree = new float[arraySize];
                layertree = new GolfCourseLayout.GolfCourseLayer?[arraySize];

                GenerateTriangles();
                //CalcVariance(leftRoot);
                //CalcVariance(rightRoot);
            }
        }

        void GenerateTriangles()
        {
            //int arraySize = 4 * width * height - 1;
            int arraySize = 2 * width * height - 1;
            triangles = new Triangle[arraySize];
            Triangle leftRoot = new Triangle(1, 0, height, 0, 0, width, 0);
            Triangle rightRoot = new Triangle(2, width, 0, width, height, 0, height);
            RecursiveGenerateTriangles(leftRoot);
            RecursiveGenerateTriangles(rightRoot);
            CalcTriangleValues();
        }

        void RecursiveGenerateTriangles(Triangle triangle)
        {
            triangles[triangle.Index] = triangle;
            if (!triangle.IsLeaf())
            {
                Triangle leftChild = triangle.LeftChild();
                if(!leftChild.IsLeaf())
                    RecursiveGenerateTriangles(triangle.LeftChild());
                Triangle rightChild = triangle.RightChild();
                if(!rightChild.IsLeaf())
                    RecursiveGenerateTriangles(triangle.RightChild());
            }
        }
        // assume array of triangles has been created
        void CalcTriangleValues()
        {
            for (int i = triangles.Length - 1; i >= 1; --i)
            {
                Triangle triangle = triangles[i];

                float variance = triangle.Variance(heightmap);
                GolfCourseLayout.GolfCourseLayer? layer = null;

                if(!triangle.IsLeaf())
                {
                    int lci = LeftChildIndex(i);
                    int rci = RightChildIndex(i);
                    if (Variance(lci) > variance)
                    {
                        variance = Variance(lci);
                    }
                    if (Variance(rci) > variance)
                    {
                        variance = Variance(rci);
                    }
                    if (lci < variancetree.Length && rci < variancetree.Length)
                    {
                        if (layertree[lci] == layertree[rci])
                        {
                            layer = layertree[lci];
                        }
                    }
                    else
                    {
                        Triangle leftChild = triangle.LeftChild();
                        Triangle rightChild = triangle.RightChild();
                        if (leftChild.Layer(layermap) == rightChild.Layer(layermap))
                        {
                            layer = leftChild.Layer(layermap);
                        }
                    }
                    variancetree[i] = variance;
                    layertree[i] = layer;
                }
                
            }
        }

        public int ParentIndex(int index)
        {
            return (index + 1) / 2;
        }

        public int LeftChildIndex(int index)
        {
            return index * 2 + 1;
        }

        public int RightChildIndex(int index)
        {
            return index * 2 + 2;
        }

        public float Variance(Triangle triangle)
        {
            return triangle.IsLeaf() ? 0.0f : variancetree[triangle.Index];
        }

        public float Variance(int index)
        {
            if(index >= variancetree.Length)
                return 0.0f;
            else
                return variancetree[index];
        }

        public bool IsLayer(Triangle triangle, GolfCourseLayout.GolfCourseLayer layer)
        {
            if (triangle.IsLeaf())
                return triangle.Layer(layermap) == layer;
            else
                return !IsMultiLayer(triangle) && layertree[triangle.Index] == layer;
        }

        public bool IsMultiLayer(Triangle triangle)
        {
            return !triangle.IsLeaf() && layertree[triangle.Index] == null;
        }
    }
}
*/
#endregion

namespace ProceduralGolf.terrain
{
    class VarianceTree
    {
        public Heightmap Heightmap { get { return heightmap; } }
        //public float[] Tree { get { return variancetree; } }
        public Triangle LeftRoot { get { return leftRoot; } }
        public Triangle RightRoot { get { return rightRoot; } }
        Triangle leftRoot;
        Triangle rightRoot;

        Heightmap heightmap;
        //GolfCourseLayout.GolfCourseLayer[,] layermap;
        float[] variancetree;
        //GolfCourseLayout.GolfCourseLayer?[] layertree;
        //Triangle[] triangles;

        int width;
        int height;

        public VarianceTree(Heightmap heightmap)
        {
            if (heightmap.Width == heightmap.Height)
            {
                this.heightmap = heightmap;
                this.width = heightmap.Width - 1;
                this.height = heightmap.Height - 1;
                int arraySize = 4 * width * height - 1;
                variancetree = new float[arraySize];

                GenerateTriangles();
                //CalcVariance(leftRoot);
                //CalcVariance(rightRoot);
            }
        }
        /*
        void CalcVariance(Triangle triangle)
        {
            float variance = triangle.Variance(heightmap);
            if (!triangle.IsLeaf())
            {
                Triangle leftChild = triangle.LeftChild();
                CalcVariance(leftChild);
                if (variancetree[leftChild.Index] > variance)
                {
                    variance = variancetree[leftChild.Index];
                }
                Triangle rightChild = triangle.RightChild();
                CalcVariance(rightChild);
                if (variancetree[rightChild.Index] > variance)
                {
                    variance = variancetree[rightChild.Index];
                }
            }
            variancetree[triangle.Index] = variance;
            triangles[triangle.Index] = triangle;
        }
        */

        void GenerateTriangles()
        {
            //int arraySize = 4 * width * height - 1;
            //triangles = new Triangle[arraySize];
            leftRoot = new Triangle(1, 0, height, 0, 0, width, 0);
            rightRoot = new Triangle(2, width, 0, width, height, 0, height);
            RecursiveGenerateTriangles(leftRoot);
            RecursiveGenerateTriangles(rightRoot);
            CalcTriangleValues();
        }

        //void RecursiveGenerateTriangles(Triangle triangle)
        //{
        //    triangles[triangle.Index] = triangle;
        //    if (!triangle.IsLeaf())
        //    {
        //        RecursiveGenerateTriangles(triangle.LeftChild());
        //        RecursiveGenerateTriangles(triangle.RightChild());
        //    }
        //}

        //void RecursiveGenerateTriangles(Triangle triangle)
        //{
        //    Queue<Triangle> triQueue = new Queue<Triangle>();
        //    triQueue.Enqueue(triangle);
        //    Triangle curTriangle;
        //    while (triQueue.Count > 0)
        //    {
        //        curTriangle = triQueue.Dequeue();
        //        triangles[curTriangle.Index] = curTriangle;
        //        if (!curTriangle.IsLeaf())
        //        {
        //            triQueue.Enqueue(curTriangle.LeftChild());
        //            triQueue.Enqueue(curTriangle.RightChild());
        //        }
        //    }
        //}

        void RecursiveGenerateTriangles(Triangle triangle)
        {
            Queue<Triangle> triQueue = new Queue<Triangle>();
            triQueue.Enqueue(triangle);
            Triangle curTriangle;
            while (triQueue.Count > 0)
            {
                curTriangle = triQueue.Dequeue();
                variancetree[curTriangle.Index] = curTriangle.Variance(heightmap);
                if (!curTriangle.IsLeaf())
                {
                    triQueue.Enqueue(curTriangle.LeftChild());
                    triQueue.Enqueue(curTriangle.RightChild());
                }
            }
        }

        // assume array of triangles has been created
        void CalcTriangleValues()
        {
            float variance;
            for (int i = variancetree.Length - 1; i >= 1; --i)
            {
                variance = variancetree[i];

                if(i < variancetree.Length / 2)
                {
                    if (variancetree[LeftChildIndex(i)] > variance)
                    {
                        variance = variancetree[LeftChildIndex(i)];
                    }
                    if (variancetree[RightChildIndex(i)] > variance)
                    {
                        variance = variancetree[RightChildIndex(i)];
                    }
                }
                variancetree[i] = variance;
            }
        }

        public int ParentIndex(int index)
        {
            return (index + 1) / 2;
        }

        public int LeftChildIndex(int index)
        {
            return index * 2 + 1;
        }

        public int RightChildIndex(int index)
        {
            return index * 2 + 2;
        }

        public float Variance(Triangle triangle)
        {
            return variancetree[triangle.Index];
        }

        //public bool IsLayer(Triangle triangle, GolfCourseLayout.GolfCourseLayer layer)
        //{
        //    return !IsMultiLayer(triangle) && layertree[triangle.Index] == layer;
        //}

        //public bool IsMultiLayer(Triangle triangle)
        //{
        //    return layertree[triangle.Index] == null;
        //}
    }
}